// hard

// 给定一个二维的字符数组board用来表示数独，其中数字1-9表示该位置已经填入了数字，.表示该位置还没有填入数字
// 现在编写一个程序，通过填充空格的方式来解决数独问题，最终不用返回答案，将题目给定board修改为可行的方案即可

// 数独解法遵循如下规则：
// 数字1-9在每一行只能出现一次
// 数字1-9在每一列只能出现一次
// 数字1-9在每一个以粗直线分隔的3*3宫格内只能出现一次

// 解题思路：使用回溯算法
// 对于每一行，每一列，每个数字，都需要循环遍历，这样就是三重循环
// 对于第i行，第j列的元素来说，如果当前位置为空位，则尝试将第k个数字置于此处，并检验数独的有效性，如果有效，则继续遍历下一个空位，直到遍历完所有空位，得到可行方案或者遍历失败时结束
// 遍历完下一个空位之后再将此位置进行回退，置位.
function backtrack(board) {
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[i].length; j++) {
            if (board[i][j] !== '.') {
                continue
            }           
            for (let k = 1; k < 10; k++) {
                if (isValid(i, j, k, board)) {
                    board[i][j] = String(k)
                    if (backtrack(board)) {
                        return true
                    }
                    board[i][j] = '.'
                }                
            } 
            return false
        }        
    }
    return true
}

function isValid(row, col, val, board) {
    for (let i = 0; i < 9; i++) {
        if (board[row][i] === String(val)) {
            return false
        }        
    }
    for (let j = 0; j < 9; j++) {
        if (board[j][col] === String(val)) {
            return false
        }        
    }
    let start_row = Math.floor(row / 3) * 3
    let start_col = Math.floor(col / 3) * 3
    for (let i = start_row; i < start_row + 3; i++) {
        for (let j = start_col; j < start_col + 3; j++) {
            if (board[i][j] === String(val)) {
                return false
            }            
        }        
    }
    return true
}

function solveSudoku(board) {
    backtrack(board)
}

let board = [
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]
]
solveSudoku(board)
console.log(board)
